package leetcode_1601_1700;

public class LeeCode_1658 {
    public static void main(String[] args) {
        System.out.println(minOperations(new int[]{1, 1, 4, 2, 3}, 5));
        System.out.println(minOperations(new int[]{3,2,20,1,1,3}, 10));
    }
    private static int minOperations(int[] nums, int x) {
        int n = nums.length;
        int[] sums1 = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sums1[i] = sums1[i - 1] + nums[i - 1];
        }
        int[] sums2 = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            sums2[i] = sums1[n] - sums1[i];
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            if (sums1[i] > x)
                break;
            int goal = x - sums1[i];
            int index = search(sums2, goal);
            if (index == -1 || index <= i - 1)
                continue;
            ans = Math.min(ans, i + n - index);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    private static int search(int[] sums2, int goal){
        int l = 0, r = sums2.length - 1;
        while (l < r){
            int m = (l + r) >> 1;
            if (sums2[m] < goal){
                r = m - 1;
            }else if (sums2[m] > goal){
                l = m + 1;
            }else {
                return m;
            }
        }
        if (sums2[l] == goal)
            return l;
        return -1;
    }
}